#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/18 17:34
# ===========================================
#       题目名称： 15. 三数之和
#       题目地址： https://leetcode.cn/problems/3sum/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================

import math


class Solution:
    """
        实现思路：
            定义三个指针 进来回切换
    """
    def threeSum(self, nums):
        # 定义返回值 最大长度
        setRes, maxLength = set(), len(nums)
        # 排序
        nums.sort()
        # 取出 超过2个非0 数值 和 超过3个的0字符
        currentIndex = 2
        while currentIndex < maxLength:
            if nums[currentIndex] != 0:
                # 不为0 普通数值 最多只能是2个
                if nums[currentIndex] == nums[currentIndex - 1] == nums[currentIndex - 2]:
                    del nums[currentIndex]
                else:
                    currentIndex += 1
            else:
                # 删除超过3个的0
                if nums.count(0) > 3:
                    del nums[currentIndex]
                else:
                    currentIndex += 1
            maxLength = len(nums)
        # print(nums)
        # 找出3个数值相加都为0的
        i, j, k = 0, 1, maxLength - 1
        while i < j < k:
            # print(i, j, k)
            target = nums[i] + nums[j]
            while j < k:
                if target + nums[k] == 0:
                    setRes.add((nums[i], nums[j], nums[k]))
                    break
                if target + nums[k] < 0:  # 如果当前值 比 最后一个值 小 就表示找不到了
                    break
                k -= 1
            # 向中心靠拢
            if j + 1 < k:
                j += 1
            else:
                if i + 1 <= maxLength - 3:
                    i += 1
                    j = i + 1
                    k = maxLength - 1
                else:
                    break
        return list([list(res) for res in setRes])

    def threeSum3(self, nums):
        """
            时间超限
        """
        res = set()
        # 排序一下
        nums.sort()
        i, j, k = 0, 1, len(nums) - 1  # 定义三个坐标
        print(nums)
        while i < j < k:
            print(i, j, k)
            if nums[i] + nums[j] + nums[k] == 0:
                res.add((nums[i], nums[j], nums[k],))
                k -= 1
            elif math.fabs(nums[i] + nums[j]) < nums[k]:
                k -= 1
            elif math.fabs(nums[i] + nums[j]) > nums[k]:
                j += 1
            else:  # 相等
                i += 1
                j = i + 1
                k = len(nums) - 1

            if j + 1 > k:
                i += 1
                j = i + 1
                k = len(nums) - 1
            if i + 1 > len(nums) - 2:
                break
        res = list(list(item) for item in res)
        return res

    def threeSum2(self, nums):
        """
            时间超限
        """
        res = set()
        # 排序一下
        nums.sort()
        i, j, k = 0, 1, len(nums) - 1  # 定义三个坐标
        print(nums)
        while i < j < k:
            print(i, j, k)
            if nums[i] + nums[j] + nums[k] == 0:
                res.add((nums[i], nums[j], nums[k],))
            if j + 1 == k != len(nums) - 1:
                j += 1
                k = len(nums) - 1
            elif j + 1 == k == len(nums) - 1:
                i += 1
                j = i + 1
                k = len(nums) - 1
            else:
                k -= 1
        res = list(list(item) for item in res)
        return res



if __name__ == '__main__':
    s = Solution()
    print("[[-1,-1,2],[-1,0,1]] =>", s.threeSum(nums=[-1, 0, 1, 2, -1, -4]))
    print("[] =>", s.threeSum(nums=[0, 1, 1]))
    print("[[0,0,0]] =>", s.threeSum(nums=[0, 0, 0]))
    print("[[0,0,0]] =>", s.threeSum(nums=[0, 0, 0, 0]))
    # [[-4,0,4],[-4,1,3],[-3,-1,4],[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,-1,2],[-1,0,1]]
    print("=>", s.threeSum(nums=[-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4]))
